The present invention relates to the field of error protection in communications systems, and more particularly to a method of cyclic redundancy check error protection that allows for varying degrees of protection, and optionally the inclusion of second channel data in a primary channel message.
Communications systems, such as a cellular telephone networks, routinely include error-control mechanisms intended to provide some degree of protection against transmission errors. Such transmission errors typically arise from external disturbances (e.g., xe2x80x9cnoisexe2x80x9d) and have the undesired effect of altering the message received.
Assuming a digital communications system, a plurality of bits to be communicated are typically collected and grouped into a packet. A packet header is typically appended to the beginning of the packet that includes various fields needed to enable and assist in the operation of various network functions. A packet trailer is typically appended to the end of the packet and typically includes, inter alia, parity bits. Together, the header, packet, and trailer is called a frame. The purpose of the parity bits carried by the frame trailer is to provide a means of detecting the presence of any bit errors introduced into the frame during the overall transmission process.
One particular method of generating and processing parity bits is the cyclic redundancy check (CRC), whose operation can be envisioned most clearly as a series of multiplication and division operations among polynomials having modulo-2 coefficients in recognition of their representation of digital bits. In this representation, the contents of a partial frame (i.e., the frame excluding its trailer) can be thought of as an N-degree polynomial, where N is the number of bits in the partial frame. This polynomial is divided by a second polynomial known as the CRC generator polynomial. On completion of the division, the resulting remainder is incorporated into the packet trailer as the parity bits, and the frame is passed on for transmission.
Upon receipt of the frame, the receiver again computes the polynomial division, and compares the resulting remainder with the received remainder. Transmission errors are indicated by any disagreement between the remainder as conveyed by the received frame and the remainder as re-computed by the receiver.
The polynomial CRC model, as well as the limitations and capabilities inherent in CRCs derived from various generator polynomials in widespread commercial use, are described more fully by Boudreau, Bergman, and Irvin, in xe2x80x9cPerformance of a cyclic redundancy check and its interaction with a data scramblerxe2x80x9d (IBM Journal of Research and Development, vol. 38, no. 6, November 1994, pp. 651-658).
With the use of CRC encoding, it is necessary for the receiving station to be aware of which generating polynomial was used to produce the incoming message in order to properly process the message. Typically a standard or universal generating polynomial of appropriate degree is used. However, this approach, which is often designed to account for worst-case scenarios, may be inefficient in the majority of situations where noise is less than worst-case conditions. For instance, a given frame might need to be sent with sixteen-bit CRC protection in noisy situations, but only eight-bit CRC protection may be required when transmission conditions improve. However, under the prior art, the sixteen-bit CRC protection is used for all situations.
In addition, it is sometimes useful to provide a low-bit-rate phantom Second channel between the transmitter and the receiver, for example, for use in exchanging network-management information, as discussed further in U.S. Pat. No. 5,862,160. Here, the term xe2x80x9cphantom channelxe2x80x9d suggests that the organization of the fixed-length framexe2x80x94in particular the frame length of the message protected by the CRCxe2x80x94does not vary as the result of providing the phantom channel. For proper functioning, it is necessary for the receiver to know when the second channel is present so that the second channel may be properly processed. One known approach is to always reserve space in the frame for this second channel. However, this approach is clearly an inefficient use of transmission capacity when the second channel is empty. Another approach is to provide an indicator flag explicitly. For example, a second-channel-present flag can be provided that explicitly tells the receiver when the second channel is not empty. However, the use of such an explicit flag approach likewise consumes transmission capacity that might otherwise be used productively.
An alternative approach is disclosed in U.S. Pat. No. 5,862,160 to Irvin and Khayrallah, which is incorporated in its entirety herein by reference. The ""160 patent describes a way in which a phantom secondary channel can be derived by deliberately inducing CRC errors. A mask that corresponds to the information to be carried by the secondary channel is exclusive-ORed (XOR) with the information to be carried by the primary channel after the CRC is computed for the primary channel information. On receipt of the altered message, the decoder detects an abnormality, as the CRC bits received do not correspond to the message received, due to the imposition of the mask. The decoder then finds the mask that unravels this imposition, and therefore restores the integrity of the CRC. That found mask then represents the intended text of the secondary channel. Although the method of the ""160 patent can be applied to some of the problems addressed by the present invention, the method of ""160 becomes prohibitively complex as the capacity of the secondary channel increases. For example, providing an eight-bit secondary channel would require the storage and processing of 256 masks.
Therefore, there remains a need for a method that provides variable levels of CRC protection that is efficient in its use of transmission resources. In addition there is a separate need for an efficient method of CRC protection that allows for secondary channels of various capacities while being efficient in its use of storage, meaning that a large catalog of masks is not required for a multi-bit secondary channel, and universal, meaning that the same method can provide both a single-bit phantom channel as well as a multi-bit secondary channel. Further, there is a need to provide these options within the context of existing systems and standards, so that their capabilities can expand and yet remain backwards-compatible.
The present method uses at least two generating polynomials, or generating codes (also known as xe2x80x9cgenerator codesxe2x80x9d), to help determine when different degrees of error protection are being employed, and optionally to detect the presence of a phantom channel on the primary channel, without the need for explicit signaling from transmitter to receiver. In essence, the receiver deduces the transmitter""s choice of CRC generating code by analyzing the incoming bit stream rather than relying on explicit signaling information and, armed with that knowledge responds accordingly.
In contrast with prior art approaches that decode the CRC encoded message using only a single generating polynomial, the present method CRC decodes the encoded message on the receive side with at least two different generating polynomials. Based on the results of the twin decoding, the present method can determine which of the generating polynomials was used to encode the message and respond accordingly. For instance, if a particular generating polynomial was used, then this may be used to indicate that a second channel has been superimposed onto the primary channel and that second channel may be extracted. On the other hand, if another generating polynomial, such as the default generating polynomial, was used, this may be used to indicate that no second channel has been superimposed. In some embodiments, the method may optionally be refined by adding additional steps to resolve potential ambiguities resulting from the use of a twin decoding scheme. These steps may include deliberately altering the primary message by XOR adding known offset polynomials to the message prior to differentiate the CRC decoding results using the different generating polynomials. The alterations may then be removed at the receive end to reconstruct the original message.
The present method increases processing overhead for at least the receiver, and typically the transmitter. Offsetting this, however, is an increase in transmission capacity. In the simplest embodiments, the present method allows the degree of redundancy in CRC encoding to be varied as necessary without the necessity of transmitting an explicit indicator flag bit or the like. In more complex embodiments, the present method allows a second channel to be phantomed onto the primary channel, once again without transmitting an explicit indicator flag bit or the like. Instead, the receiver deduces the transmitter""s choice of CRC generating code, and thus the degree of redundancy and/or presence of the second channel, by analyzing the incoming bit stream rather than relying on explicit signaling information.